第53章格雷编码

格雷编码(Gray Code)是一种特殊的二进制编码方式，其核心特性是相邻的两个编码之间仅有一位二进制数不同，且首尾两个编码也满足这一特性(形成循环)。

53.1 格雷编码的基本概念

53.1.1 定义

格雷编码是一个二进制数字系统；其中任意两个连续的数值仅有一位二进制数不同，且第一个和最后一个数值也仅有一位不同(构成循环格雷码)。示例：3位格雷编码序列为：000、001、011、010、110、111、101、100。相邻编码对000与100第0位不同、001与011第1位不同、011与010第0位不同，以此类推。首尾对比：000与100(第2位不同)，满足循环特性。

53.1.2 特点

相邻性：任意两个连续编码的二进制表示中，仅有一个bit位不同。
循环性：序列的第一个编码和最后一个编码也仅有一个bit位不同。
唯一性： $n$ 位格雷编码包含 $2^{n}$ 个不同的编码，覆盖0到 $2^{n}-1$ 的所有整数。
无歧义性：编码转换时，相邻状态的切换仅涉及一位变化，可减少信号干扰导致的歧义。

53.2 格雷编码的数学性质

53.2.1 二进制编码的转换关系

$n$ 位二进制数 $B$ $(b_{n-1} b_{n-2} ... b_{1} b_{0})$ 与对应的格雷码 $G$ $(g_{n-1} g_{n-2} ... g_{1} g_{0})$ 存在明确的转换规则：二进制转格雷码：

最高位相同： $g_{n-1}=b_{n-1}$
其他位： $g_{i}=b_{i+1} \text{ XOR } b_{i}$ ， $i=0,1,...,n-2$ ，其中XOR为异或运算(相同为0，不同为1)。
公式简化： $G=B \text{ XOR } (B \gg 1)$

格雷码转二进制：

最高位相同： $b_{n-1}=g_{n-1}$
其他位： $b_{i}=b_{i+1} \text{ XOR } g_{i}$ ， $i=0,1,...,n-2$ 。
公式实现：从最高位开始，逐位与格雷码对应位异或。

示例：二进制数 $B=1010$ (十进制10)转格雷码

B \gg 1=0101,\quad G=1010 \text{ XOR } 0101=1111

格雷码 $G=1111$ 转二进制：

b_{3}=1,\quad b_{2}=1 \text{ XOR } 1=0,\quad b_{1}=0 \text{ XOR } 1=1,\quad b_{0}=1 \text{ XOR } 0=0

最终二进制 $B=1010$ (十进制10)。

53.2.2 递推性质

$n$ 位格雷编码可由 $n-1$ 位格雷编码通过镜像反射法生成，体现递归特性： $n=1$ 时，格雷编码为[0,1]。 $n>1$ 时：

将 $n-1$ 位格雷编码序列作为前半部分，每个编码前加0。
将 $n-1$ 位格雷编码序列反转作为后半部分，每个编码前加1。
合并两部分得到 $n$ 位格雷编码序列。

示例： $n=2$ 时，基于 $n=1$ 的序列[0,1]生成：前半部分(加0)：00,01。后半部分(反转加1)：11,10。合并后：[00, 01,11,10]。

53.3 格雷编码的生成方法

53.3.1 二进制转换法

利用转换公式 $G=B \text{ XOR } (B \gg 1)$ 直接生成 $n$ 位格雷编码序列。

#include <vector>
using namespace std;
vector<int> generateGrayCode (int n) {
    int size = 1 << n;
    vector<int> gray;
    for (int i=0;i<size; i++){
        gray.push_back(i ^ (i>>1));
    }
    return gray;
}

示例： $n=3$ 时，生成序列为[0, 1, 3,2,6,7,5,4]，对应二进制格雷码 [000, 001, 011, 010, 110, 111, 101, 100]。

53.3.2 镜像反射法

基于递推性质，通过递归生成格雷编码。

#include <vector>
#include <algorithm>
using namespace std;
vector<int> grayCode (int n) {
    vector<int> result;
    if (n==0){
        result.push_back(0);
        return result;
    }
    vector<int> prev = grayCode (n -1);
    result = prev;
    reverse (prev.begin(), prev.end());
    int add = 1 << (n -1);
    for (int num:prev){
        result.push_back(num + add);
    }
    return result;
}

示例： $n=2$ 时，递归生成过程为： $n=1$ 输出[0,1]。镜像反转prev→[1,0]，加 $1<<1=2$ →[3,2]。合并得[0,1,3,2]。

53.3.3 循环移位法

初始编码为0。每次向右循环移动1位，与原编码异或后得到下一个编码。重复 $2^{n}-1$ 次，得到完整序列。

#include <vector>
using namespace std;
vector<int> grayCodeByShift(int n) {
    vector<int> gray;
    int size=1<<n;
    int current=0;
    for (int i=0;i<size; i++) {
        gray.push_back(current);
        int lsb=current&1;
        current = (current>>1)|(lsb<<(n -1));
        current ^= gray[0];
    }
    return gray;
}

53.4 应用场景

数字通信：减少信号传输噪声干扰，相邻编码仅切换一位，降低误码率。
机械控制：电机转角、旋转编码器使用格雷码，避免位置检测出现中间误判状态。
模拟-数字转换(ADC)：平滑模拟量转数字量的过渡，减少量化误差。
卡诺图(Kamaugh图)：单元格相邻规则与格雷编码匹配，方便逻辑化简。
测试与故障检测：利用单比特变化特性快速定位单比特错误。

53.1 格雷编码的基本概念​

53.1.1 定义​

53.1.2 特点​

53.2 格雷编码的数学性质​

53.2.1 二进制编码的转换关系​

53.2.2 递推性质​

53.3 格雷编码的生成方法​

53.3.1 二进制转换法​

53.3.2 镜像反射法​

53.3.3 循环移位法​

53.4 应用场景​